#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
typedef struct {
	int v1;
	int v2;
	float weight;
} Edge;

struct list_edge {
	Edge edge;
	struct list_edge * next;
};

list_edge * curr, *head, *mstTree;
int number_edges = 4;
int number_vertexs;
int* root;
int* size;
void printData(list_edge * list) {
	list_edge *a = list;
	while (a->next!=NULL) {
		printf("%d-------------%d----------------%f\n", a->edge.v1, a->edge.v2,
				a->edge.weight);
		a = a->next;
	}
}

void init_graph() {
	FILE * pFile;
	int i;
	head = NULL;
	//read
	pFile = fopen("tinyEWG.txt", "r");
	fscanf(pFile, "%d", &number_vertexs);
	fscanf(pFile, "%d", &number_edges);
	root = (int*) malloc(number_vertexs * sizeof(int));
	size = (int*) malloc(number_vertexs * sizeof(int));
	head = (list_edge*) malloc(sizeof(list_edge));
	curr=head;
	for (i = 0; i < number_edges; i++) {
		list_edge * newEdge= (list_edge*) malloc(sizeof(list_edge));
		fscanf(pFile, "%d", &curr->edge.v1);
		fscanf(pFile, "%d", &curr->edge.v2);
		fscanf(pFile, "%f", &curr->edge.weight);
		newEdge->next=NULL;
		curr->next = newEdge;
		curr=newEdge;
	}

	//print data

	printData(head);

	//init root

	for (i = 0; i < number_vertexs; i++) {
		root[i] = i;
		size[i]=1;
	}
}
int findRoot(int i) {
	//find root
	while (i != root[i]) {
		i = root[i];
	}
	return i;
}
int less(Edge e, Edge f) {
	return (e.weight < f.weight);

}
void unionEdge(int i, int j) {

	if (i == j) {
		return;
	}

	// make smaller root point to larger one
	if (size[i] < size[j]) {
		root[i] = j;
		size[j] += size[i];
	} else {
		root[j] = i;
		size[i] += size[j];
	}
}
void boruvkaMst() {
	list_edge *tree;
	Edge* closest = (Edge *) malloc(number_vertexs * sizeof(Edge));
	mstTree = (list_edge*) malloc(sizeof(list_edge));
	tree=mstTree;
	int mstTreeSize = 0;
	int countEdge=0;
	int countLoop=0;
	do {
		for (int i = 0; i < number_vertexs; i++) {
			closest[i].weight= -1;
		}
		curr = head;
		//find closest edge
		while (curr->next!=NULL) {
			int i = findRoot(curr->edge.v1);
			int j = findRoot(curr->edge.v2);
			if (i == j) {
				curr = curr->next;
				continue;
			}
			if (closest[i].weight == -1
					||curr->edge.weight < closest[i].weight) {
				closest[i] = curr->edge;
			}
			if (closest[j].weight == -1
					|| curr->edge.weight < closest[j].weight) {
				closest[j] = curr->edge;
			}
			curr = curr->next;
		}
		countEdge=0;
		for (int i = 0; i < number_vertexs; i++) {
			Edge e = closest[i];
			if (e.weight != -1) {
				int u = findRoot(e.v1);
				int v = findRoot(e.v2);
				if (u!= v) {
					countEdge++;
					list_edge* newEdge = (list_edge*) malloc(sizeof(list_edge));
					tree->edge=e;
				    tree->next = newEdge;
					tree=newEdge;
					mstTreeSize++;
					unionEdge(u, v);
				}
			}
		}
		countLoop++;
	}
	while(mstTreeSize<number_vertexs-1);
   printf("number loop :%d\n",countLoop);
}
int main() {
	init_graph();
	printf("-------------------------------------------------------\n");
	boruvkaMst();
	printData(mstTree);
	return 0;
}
